#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include "constants.h"
#include "classes.h"
#include "data_io.h"

using namespace std;

void SiteInfo::add_site(string site_name, int bw_upper)
{
    this->site_names.push_back(site_name);
    this->site_name_to_id[site_name] = this->N++;
    this->site_to_clients.push_back(vector<int>());
    this->site_connect_num.push_back(0);
    this->site_bw_upper.push_back(bw_upper);
};

void SiteInfo::add_connect(int site_id, int client_id)
{
    this->site_to_clients[site_id].push_back(client_id);
    this->site_connect_num[site_id]++;
};

void ClientInfo::add_client(string client_name)
{
    this->client_names.push_back(client_name);
    this->client_name_to_id[client_name] = this->M++;
    this->client_to_sites.push_back(vector<int>());
    this->client_connect_num.push_back(0);
};

void ClientInfo::add_connect(int client_id, int site_id)
{
    this->client_to_sites[client_id].push_back(site_id);
    this->client_connect_num[client_id]++;
};

TDemand::TDemand(int t)
{
    this->t = t;
    this->P = 0;
};

void TDemand::add_stream(string stream_name)
{
    this->stream_name_vec.push_back(stream_name);
    this->stream_name_to_ids[stream_name] = this->P++;
    this->sorted_stream_deamnd_bw.push_back(vector<BandwidthNode>());
};

void TDemand::add_demand(const int &stream_id, const int &client_id, const int &demand_bw)
{
    this->demand_bw_matrix[stream_id][client_id] = demand_bw;
    this->sorted_deamnd_bw.push_back(BandwidthNode(stream_id, client_id, demand_bw));
    this->sorted_stream_deamnd_bw[stream_id].push_back(BandwidthNode(stream_id, client_id, demand_bw));
}

void DemandInfo::add_demand(TDemand *tdemand)
{
    auto cmp_func = [](const BandwidthNode &bw1, const BandwidthNode &bw2)
    { return bw1.bandwidth > bw2.bandwidth; };

    sort(tdemand->sorted_deamnd_bw.begin(), tdemand->sorted_deamnd_bw.end(), cmp_func);

    for (int stream_id = 0; stream_id < tdemand->P; stream_id++)
    {
        auto &stream_demands = tdemand->sorted_stream_deamnd_bw[stream_id];
        sort(stream_demands.begin(), stream_demands.end(), cmp_func);
    }

    this->demand_vec.push_back(tdemand);
    this->T++;
};

void ConfigInfo::set_quantile_index(int T)
{
    this->quantile_index = ceil(QUANTILE * T) - 1;
};

BandwidthNode::BandwidthNode(int stream_id, int client_id, int bandwidth)
{
    this->stream_id = stream_id;
    this->client_id = client_id;
    this->bandwidth = bandwidth;
}

void SiteAlloInfo::add_allocate(AlloNode *allo_node)
{
    int &bw = allo_node->bandwidth;
    if (!this->count)
    {
        this->largest_bw = bw;
        this->head = allo_node;
        this->tail = allo_node;
    }
    else if (bw > this->largest_bw)
    {
        this->largest_bw = bw;
        allo_node->next_site_allo = this->head;
        this->head->pre_site_allo = allo_node;
        this->head = allo_node;
    }
    else
    {
        AlloNode *p = this->head->next_site_allo;
        while (p && (bw <= p->bandwidth))
        {
            p = p->next_site_allo;
        }
        if (!p)
        {
            allo_node->pre_site_allo = this->tail;
            this->tail->next_site_allo = allo_node;
            this->tail = allo_node;
        }
        else
        {
            allo_node->pre_site_allo = p->pre_site_allo;
            allo_node->next_site_allo = p;
            p->pre_site_allo->next_site_allo = allo_node;
            p->pre_site_allo = allo_node;
        }
    }
    this->bw_sum += bw;
    this->count++;
}

void SiteAlloInfo::drop_allocate(AlloNode *allo_node)
{
    int &bw = allo_node->bandwidth;
    if (this->count == 1)
    {
        this->largest_bw = 0;
        this->head = NULL;
        this->tail = NULL;
    }
    else if (allo_node == this->head)
    {
        this->head = this->head->next_site_allo;
        this->head->pre_site_allo = NULL;
        this->largest_bw = this->head->bandwidth;
    }
    else if (allo_node == this->tail)
    {
        this->tail = this->tail->pre_site_allo;
        this->tail->next_site_allo = NULL;
    }
    else
    {
        allo_node->pre_site_allo->next_site_allo = allo_node->next_site_allo;
        allo_node->next_site_allo->pre_site_allo = allo_node->pre_site_allo;
    }

    allo_node->site_id = -1;
    allo_node->pre_site_allo = NULL;
    allo_node->next_site_allo = NULL;
    this->bw_sum -= bw;
    this->count--;
}

SiteAlloSortIter::SiteAlloSortIter(SiteAlloInfo (&stream_allo_list)[MAX_P], bool asc)
{
    this->asc = asc;
    AlloNode *p;
    if (asc)
    {
        for (int stream_id = 0; stream_id < MAX_P; ++stream_id)
        {
            p = stream_allo_list[stream_id].tail;
            if (p)
            {
                this->point_list.push_back(p);
            }
        }
    }
    else
    {
        for (int stream_id = 0; stream_id < MAX_P; ++stream_id)
        {
            p = stream_allo_list[stream_id].head;
            if (p)
            {
                this->point_list.push_back(p);
            }
        }
    }
}

void SiteAlloSortIter::next(AlloNode *&allo_node)
{
    allo_node = NULL;
    if (this->asc)
    {
        int _min_bw = 100000000;
        list<AlloNode *>::iterator _min_iter;

        for (auto iter = this->point_list.begin(); iter != this->point_list.end(); ++iter)
        {
            if ((*iter)->bandwidth < _min_bw)
            {
                allo_node = (*iter);
                _min_bw = allo_node->bandwidth;
                _min_iter = iter;
            }
        }

        if (allo_node)
        {
            (*_min_iter) = allo_node->pre_site_allo;
            if (!(*_min_iter))
            {
                this->point_list.erase(_min_iter);
            }
        }
    }
    else
    {
        int _max_bw = -1;
        list<AlloNode *>::iterator _max_iter;

        for (auto iter = this->point_list.begin(); iter != this->point_list.end(); ++iter)
        {
            if ((*iter)->bandwidth > _max_bw)
            {
                allo_node = (*iter);
                _max_bw = allo_node->bandwidth;
                _max_iter = iter;
            }
        }

        if (allo_node)
        {
            (*_max_iter) = allo_node->next_site_allo;
            if (!(*_max_iter))
            {
                this->point_list.erase(_max_iter);
            }
        }
    }
}

AssignOpt::AssignOpt(int opt_type, int stream_id, int client_id, int site_id)
{
    this->opt_type = opt_type;
    this->stream_id = stream_id;
    this->client_id = client_id;
    this->site_id = site_id;
}

TAssign::TAssign(TDemand *tdemand)
{
    this->tdemand = tdemand;
    this->t = tdemand->t;
    this->P = tdemand->P;

    for (int stream_id = 0; stream_id < this->P; stream_id++)
    {
        for (int client_id = 0; client_id < M; client_id++)
        {
            AlloNode &allo_node = this->stream_client_to_allo_node[stream_id][client_id];
            allo_node.stream_id = stream_id;
            allo_node.client_id = client_id;
            allo_node.bandwidth = tdemand->demand_bw_matrix[stream_id][client_id];
        }
    }

    this->snapshot_opt_history = new list<AssignOpt>();
};

void TAssign::add_allocate(int stream_id, int client_id, int site_id)
{
    if (this->record_snapshot)
    {
        this->snapshot_opt_history->push_front(AssignOpt(0, stream_id, client_id, site_id));
    }

    AlloNode &allo_node = this->stream_client_to_allo_node[stream_id][client_id];
    int &bw = allo_node.bandwidth;
    if (!bw)
    {
        return;
    }

    this->site_allocated_bw[site_id] += bw;
    this->site_total_bw[site_id] += bw;

    SiteAlloInfo &site_allo_info = this->site_stream_to_allo_info[site_id][stream_id];
    int &largest_bw = site_allo_info.largest_bw;
    if (bw > largest_bw)
    {
        this->center_site_bw += (bw - largest_bw);
    }

    allo_node.site_id = site_id;
    site_allo_info.add_allocate(&allo_node);
};

void TAssign::drop_allocate(int stream_id, int client_id)
{
    AlloNode &allo_node = this->stream_client_to_allo_node[stream_id][client_id];
    int &bw = allo_node.bandwidth;
    int &site_id = allo_node.site_id;

    if (this->record_snapshot)
    {
        this->snapshot_opt_history->push_front(AssignOpt(1, stream_id, client_id, site_id));
    }

    this->site_allocated_bw[site_id] -= bw;
    this->site_total_bw[site_id] -= bw;

    SiteAlloInfo &site_allo_info = this->site_stream_to_allo_info[site_id][stream_id];
    allo_node.site_id = -1;
    if (site_allo_info.head == (&allo_node)) // 如果要删除的是最大流
    {
        site_allo_info.drop_allocate(&allo_node);
        this->center_site_bw -= (bw - site_allo_info.largest_bw);
    }
    else
    {
        site_allo_info.drop_allocate(&allo_node);
    }
}

void TAssign::transfer(int stream_id, int client_id, int to_site_id)
{
    this->drop_allocate(stream_id, client_id);
    this->add_allocate(stream_id, client_id, to_site_id);
};

void TAssign::refresh_inherited_bw()
{
    // 第一个时刻没有上一时刻，因此跳过
    if (!this->pre_tassign)
    {
        return;
    }

    for (int site_id = 0; site_id < N; site_id++)
    {
        this->site_inherited_bw[site_id] = floor(this->pre_tassign->site_total_bw[site_id] * INHERIT_RATE);
    }
};

void TAssign::refresh_total_bw()
{
    for (int site_id = 0; site_id < N; site_id++)
    {
        this->site_total_bw[site_id] = this->site_allocated_bw[site_id] + this->site_inherited_bw[site_id];
    }
};

void TAssign::snapshot()
{
    this->record_snapshot = true;
}

void TAssign::restore()
{
    this->record_snapshot = false;
    for (auto &opt : *this->snapshot_opt_history)
    {
        switch (opt.opt_type)
        {
        case 0:
            this->drop_allocate(opt.stream_id, opt.client_id);
            break;
        case 1:
            this->add_allocate(opt.stream_id, opt.client_id, opt.site_id);
            break;
        default:
            cout << "ERROR: unknown opt type:" << opt.opt_type << endl;
            throw exception();
        }
    }
    this->snapshot_opt_history->clear();
}

void TAssign::cancel_snapshot()
{
    this->record_snapshot = false;
    this->snapshot_opt_history->clear();
}

AssignInfo::AssignInfo(DemandInfo &demand_info)
{
    TAssign *pre_tassign = NULL;
    TAssign *current_tassign = NULL;

    for (auto &tdemand : demand_info.demand_vec)
    {
        current_tassign = new TAssign(tdemand);
        current_tassign->pre_tassign = pre_tassign;
        if (pre_tassign)
        {
            pre_tassign->next_tassign = current_tassign;
        }
        this->assign_vec.push_back(current_tassign);
        pre_tassign = current_tassign;
    }
    pre_tassign->next_tassign = NULL;
};